from typing import List
# nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
# 输出：[1, 2, 2, 3, 5, 6]

#双指针
#倒序比较
class Solution:#单增
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i = m - 1
        j = n - 1
        k = m + n - 1
        while i>=0 or j>=0:#都结束后
            if i==-1:#nums1都结束了，剩下都是用nums2来填充
                nums1[k] = nums2[j]
                j=j-1
            elif j==-1:
                nums1[k]=nums1[i]
                i=i-1
            elif nums2[j]>=nums1[i]:
                nums1[k]=nums2[j]
                j=j-1
            else:
                nums1[k]=nums1[i]
                i=i-1
            k = k - 1
        print(nums1)

def main():
    S=Solution()
    # a=[1,2,3,0,0,0]
    a=[0]
    m=0
    b=[1]
    n=1
    S.merge(a,m,b,n)
main()
# outpt:[1, 2, 2, 3, 5, 6]